package com.algorithm.Heap;

import printer.BinaryTreeInfo;
import printer.BinaryTrees;

import java.util.Comparator;

public class BinaryHeap<E> extends AbstractHeap<E>{
    private static final int DEFAULT_CAPACITY = 10;
    private E[] elements;

    public BinaryHeap() {
        this(null,null);
    }

    public BinaryHeap(E[] element) {
        this(element,null);
    }

    public BinaryHeap(Comparator<E> comparator) {
        this(null,comparator);
    }

    public BinaryHeap(E[] element,Comparator<E> comparator)
    {
        super(comparator);
        if (element == null) {
            this.elements = (E[])new Object[DEFAULT_CAPACITY];
        }else {
            int elementSize = Math.max(DEFAULT_CAPACITY,element.length);
            this.elements = (E[])new Object[elementSize];
            System.arraycopy(element, 0, elements, 0, element.length);
            size = element.length;
            heapify();
        }
    }


    @Override
    public void clear() {
        for (int i = 0; i < elements.length; i++) {
            elements[i] = null;
        }
        size = 0;
    }

    @Override
    public void add(E element) {
        elementNotNullCheck(element);
        expandSize(size+1);
        elements[size++] = element;
        siftUp(size-1);
    }

    @Override
    public E get() {
        emptyCheck();
        return elements[0];
    }

    @Override
    public E remove() {
        emptyCheck();
        E first = elements[0];
        int lastIndex = --size;
        elements[0] = elements[lastIndex];
        elements[lastIndex] = null;
        siftDown(0);
        return first;
    }

    @Override
    public E replace(E element) {
        E top = null;
        if (size == 0) {
            elements[size++] = element;
        }else {
            top = elements[0];
            elements[0] = element;
            siftDown(0);
        }
        return top;
    }

    /**
     * parent Node is (i-1)/2
     */
    private void siftUp(int index) {
        E element = elements[index];
        while (index>0) {
            int parentIndex = (index-1) >> 1;
            E parent = elements[parentIndex];
            if (compare(element,parent) <= 0) return;

            E tmp = elements[parentIndex];
            elements[parentIndex] = element;
            elements[index] = tmp;
            index = parentIndex;
        }
    }


    /**
     * 上滤
     * 左子节点的索引为2i+1，2i+1 > n -1 没有做子节点
     * 右子节点的索引为2i+2，2i+2 > n -1 没有做子节点
     * 完全二叉树的非叶子节点的数量size/2
     */
    private void siftDown(int index) {
        E ele = elements[index];
        int half = size >> 1;
        while (index < half) {
            int childIndex = (index << 1) + 1;
            E child = elements[childIndex];
            int rightIndex = childIndex + 1;
            if (rightIndex < size && compare(elements[rightIndex],child) > 0) {
                child = elements[childIndex = rightIndex];
            }

            if (compare(ele,child) >= 0) break;
            elements[index] = child;
            index = childIndex;
        }
        elements[index] = ele;
    }

    private void heapify() {
        for (int i = (size >> 1) - 1; i >= 0; i--) {
            siftDown(i);
        }
    }

    private void expandSize(int capacity) {
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        E[] newElements = (E[])new Object[newCapacity];
        System.arraycopy(elements, 0, newElements, 0, elements.length);
        this.elements = newElements;
    }

    private int compare(E ele1,E ele2) {
        return comparator != null ? comparator.compare(ele1,ele2) : ((Comparable)ele1).compareTo(ele2);
    }

    public void print() {
        BinaryTreeInfo binaryTreeInfo = new BinaryTreeInfo() {
            @Override
            public Object root() {
                return 0;
            }

            @Override
            public Object left(Object node) {
                int index = ((int)node << 1) + 1;
                return index >= size ? null : index;
            }

            @Override
            public Object right(Object node) {
                int index = ((int)node << 1) + 2;
                return index >= size ? null : index;
            }

            @Override
            public Object string(Object node) {
                return elements[(int)node];
            }
        };
        BinaryTrees.println(binaryTreeInfo);
    }
}
